小清新 dp 题喜加一。
题意:我们有一个字符串 ,长度为 。我们可以在任意位置添加或删除一个字母,共有 个字母可供选择,添加或删除不同字母所需花费不同,求使这个字符串为回文串的最少花费。
显然区间 dp,设计状态 表示使 为回文串所需的最少花费。
下面考虑状态转移:
我们枚举区间长度 ,然后枚举左端点 ,得到右端点 。
对于一个回文字符串,在它的左侧加一个字符后要想保持回文性,有两种方法:在右侧添加一个同样的字符,或者将左侧字符删去。可以看出,对于一个字符而言,插入和删除的权值没有区别,可以只存最小值。
考虑这个字符串,我们可以看做它是由回文串在左侧添加一个字符得到的,也可以看做它是在右侧添加一个字符得到的。我们选择这两者的更小的那个即可:( 表示对于一个字符,插入和删除的权值中小的那个)
当然,有一种情况较为特殊:,此时我们需要特判。如果 ,则该串本身回文, 。否则,。
于是,我们便得到了本题的三个方程。
代码:
//By: Luogu@rui_er(122461)
#include <bits/stdc++.h>
using namespace std;
const int M = 2005;
int n, m;
string s;
map<char, int> mp;
int dp[M][M];
int main() {
scanf("%d%d", &n, &m);
cin>>s;
memset(dp, 0x3f, sizeof(dp));
for(int i=0;i<m;i++) {
for(int j=0;j<=i;j++) dp[i][j] = 0;
}
for(int i=1;i<=n;i++) {
char c = getchar();
for(;c==' '||c=='\n';c=getchar());
int a, b;
scanf("%d%d", &a, &b);
mp[c] = min(a, b);
}
for(int l=0;l<m;l++) {
for(int i=0,j=l;j<m;i++,j++) {
dp[i][j] = min(dp[i+1][j]+mp[s[i]], dp[i][j-1]+mp[s[j]]);
if(s[i] == s[j]) dp[i][j] = min(dp[i][j], (l <= 1 ? 0 : dp[i+1][j-1]));
}
}
printf("%d\n", dp[0][m-1]);
return 0;
}